// https://leetcode.cn/problems/fibonacci-number/description/

// 算法思路总结：
// 1. 记忆化搜索实现斐波那契数列计算
// 2. 使用memo数组存储已计算的斐波那契数
// 3. 基准情况：n=0返回0，n=1返回1
// 4. 递归关系：f(n) = f(n-1) + f(n-2)
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int memo[31];
    int fib(int n) 
    {
        memset(memo, -1, sizeof(memo));

        return dfs(n);
    }

    int dfs(int n)
    {
        if (memo[n] != -1) return memo[n];
        if (n <= 1)
        {
            memo[n] = n;
            return memo[n];
        }

        memo[n] = dfs(n - 1) + dfs(n - 2);
        return memo[n];
    }
};

int main()
{
    int n1 = 1, n2 = 2, n3 = 3;
    Solution sol;

    cout << sol.fib(n1) << endl;
    cout << sol.fib(n2) << endl;
    cout << sol.fib(n3) << endl;

    return 0;
}